import Random._

def indexOfMinInRange(a:Array[Int],b:Int,c:Int):Int= {
    var j=b 
    for(i<-(b+1) until c) {
        if(a(i)<a(j)) {
            j=i
        }
    }
    return j
}

def swapIndices(a:Array[Int],b:Int,c:Int) ={
    var t=a(b)
    a(b)=a(c)
    a(c)=t
}

def selectionSort(a:Array[Int]):Array[Int]= {
    for(i<-0 until a.length) {
        var k=indexOfMinInRange(a,i,a.length)
        swapIndices(a,k,i)
    }
    a
}

def genRandom(limit:Int,arSize:Int):Array[Int]= {
    var toRet=new Array[Int](arSize)    
    for(i<-0 until arSize) {
            toRet(i)=Random.nextInt(limit)
    }
    return toRet
}
def bubbleSort(a:Array[Int]):Array[Int] ={
    var i=0
    var j=0
    var c=0
    for(i<-0 until a.length-1) {
        for(j<-0 until a.length-1-i) {
            if(a(j)>a(j+1)) {
                swapIndices(a,j,j+1)
            }
            c=c+1
        }
    }
    a
}
def isSorted(a:Array[Int]):Boolean= {
    for(i<-0 to (a.length-2)) {
        if(a(i)>a(i+1)) return false           
    }
    return true
}
def quickSort(xs:Array[Int]):Array[Int] = {
    def partition(low:Int,high:Int) ={
        var j=low
        for(i<-low to high) {
            if(xs(i)<xs(low)) {//C
                swapIndices(xs,i,j+1)
                j+=1
            }
        }
        swapIndices(xs,j,low)
        j
    }
    def qsort1(low:Int,high:Int):Unit = {
        if(low>=high) return //empty array or array with only one element is 
        //sorted
        else {
            var m=partition(low,high) 
            qsort1(low,m-1)
            qsort1(m+1,high)
        }
    }
    qsort1(0,xs.length-1)
    return xs
}

 test("The arrays are sorted") {
    def testAlgorithm(func:(Array[Int])=>Array[Int])= {
        func(Array()) should equal (Array())
        func(Array(4)) should equal (Array(4))
        func(Array(6,5,4,3,2,1)) should equal (Array(1,2,3,4,5,6))
        func(Array(9,9,6,6)) should equal(Array(6,6,9,9))
        var testRan=genRandom(100,1000)
        println("sorting and verifying array of size 1000")
        assert(isSorted(func(testRan)))
    }
    testAlgorithm(selectionSort)
    testAlgorithm(bubbleSort)
    testAlgorithm(quickSort)
    testAlgorithm(insertionSort)
    testAlgorithm(isort) 
    testAlgorithm(mergeSort)
} 
def insertionSort(xs:Array[Int]):Array[Int]= {
    for(i<- 0 until xs.length) {
        for(k<-0 until i) {
            if(xs(i)<=xs(k)) {
                swapIndices(xs,i,k)
            }
        }
    }
    xs    
}
def isort(xs:Array[Int]):Array[Int] = {
    def insertInSortedArray(index:Int):Unit= {
        for(i<-index until 0 by -1) {
            if(xs(i)<xs(i-1)) {
                swapIndices(xs,i,i-1)
            }
            else{
                return
            }
        }
    }
    for(i<-0 until xs.length) {
        insertInSortedArray(i)
    }
    xs
}
def merge(xs:Array[Int],low:Int,mid:Int,high:Int):Array[Int]= {
    var temp=new Array[Int](high-low+1)
    var i=low
    var j=mid+1
    var k=0
    while(i!=mid+1 && j!=high+1) {
        if(xs(i)>xs(j)) {
            temp(k)=xs(j)
            j+=1
        }
        else {
            temp(k)=xs(i)
            i+=1
        }
        k+=1 
    }
    if(i!=mid+1) {
        while(k<temp.length) {
            temp(k)=xs(i)
            k+=1
            i+=1
        }
    }
    else{
        var l=0
        while(k<temp.length) {
            temp(k)=xs(j) 
            k+=1
            j+=1
        }
    }
    for(h<-low to high) {
        xs(h)=temp(h-low)
    }
    xs
} 
ignore("Merge works") {
    merge(Array(1,2,3,4,5,6,7,8),0,3,7)should equal (Array(1,2,3,4,5,6,7,8))
    merge(Array(5,6,7,8,1,2,3,4),0,3,7)should equal (Array(1,2,3,4,5,6,7,8))
    merge(Array(2,4,6,8,1,3,7),0,3,6)should equal (Array(1,2,3,4,6,7,8))
} 

def mergeSort(xs:Array[Int]):Array[Int]= {
    def msort1(low:Int,high:Int):Unit= {
          if(low>=high) return
          else {
              var mid=(low+high)/2
              msort1(low,mid)
              msort1(mid+1,high)
              merge(xs,low,mid,high)
          }
    }
    msort1(0,xs.length-1)
    xs
}


        



